package 链表与双指针.m03.d12.t01;

import 链表与双指针.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode left = head, right = slow.next;
        slow.next = null;
        ListNode l = sortList(left);
        ListNode r = sortList(right);
        ListNode res = merge(l, r);
        return res;
    }
    
    public ListNode merge(ListNode l, ListNode r) {
        ListNode h = new ListNode(), res = h, A = l, B = r;
        while(A!=null && B!=null) {
            ListNode Atmp = A.next;
            ListNode Btmp = B.next;
            if(A.val <= B.val) {
                h.next = A;
                A = Atmp;
            } else {
                h.next = B;
                B = Btmp;
            }
            h = h.next;
        }
        if(A!=null) {
            h.next = A;
        }
        if(B!=null) {
            h.next = B;
        }
        return res.next;
    }
}